package 力扣;

/**
 * @author yyq
 * @create 2022-03-01 19:45
 */
public class leetcode300 {
    public static void main(String[] args) {
        int[] s={1,3,6,7,9,4,10,5,6};
        System.out.println(lengthOfLIS(s));

    }
    public static int lengthOfLIS(int[] nums) {
        // 定义dp[i] 为 0-i中最长递归子串
        int[] dp=new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i]=1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j=0;j<i;j++){
                if(nums[i]>nums[j]) {
                    if(dp[i]<=dp[j]){
                        dp[i]=dp[j]+1;
                    }
                }
            }
        }
        int max=dp[0];
        for (int i = 1; i < dp.length; i++) {
            if(dp[i]>max) max=dp[i];
            System.out.print("dp:"+dp[i]+" ");
        }
        System.out.println();

        return max;
    }
}
